#include <vector>
#include <queue>

using namespace std;

// 电动车游城市
// 小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间
// 小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1
// 他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，
// 表示城市 A、B 间存在双向通路。
// 初始状态，电动车电量为 0。每个城市都设有充电桩，
// charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
// 请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end
// 测试链接 : https://leetcode.cn/problems/DFPeFJ/

// 本题的扩出来的点是【到达的城市，到达该城市时的电量】
class Solution 
{
public:
    // cnt：电动车电量上限
    int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) 
    {
        int n = charge.size();
        vector<vector<pair<int, int>>> g(n);
        // 建图
        for(auto& path : paths)
        {
            g[path[0]].emplace_back(path[1], path[2]);
            g[path[1]].emplace_back(path[0], path[2]);
        }

        // 0 ~ n - 1 不代表图上的点
        // （点，到达这个点的电量）才是图上的点！
        int dist[n][cnt + 1];
        memset(dist, 0x3f, sizeof(dist));
        bool visited[n][cnt + 1];
        memset(visited, 0, sizeof(visited));
        // 0 : 花费时间
		// 1 : 当前点
		// 2 : 来到当前点的电量
        // 将花费时间放在 0 位置的目的是，能使用标准库中实现的比较器
        // 库中的比较器是依次比较 0,1,2 位置上的数字大小，直至比较出结果
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> q;
        q.emplace(0, start, 0);
        while(!q.empty())
        {
            auto [cost, cur, power] = q.top();
            q.pop();
            if(visited[cur][power]) continue;
            // 常见剪枝
            // 发现终点直接返回
            // 不用等都结束
            if(cur == end) return cost;
            visited[cur][power] = true;
            // 冲一格电
            // cur, power + 1
            if(power < cnt)
            {

                if(!visited[cur][power + 1] && cost + charge[cur] < dist[cur][power + 1])
                {
                    dist[cur][power + 1] = cost + charge[cur];
                    q.emplace(cost + charge[cur], cur, power + 1);
                }

            }
            // 不充电去别的城市
            for(auto& [nextCity, distance] : g[cur])
            {
                int restPower = power - distance;
                int nextCost = cost + distance;
                if(restPower >= 0 && !visited[nextCity][restPower] && nextCost < dist[nextCity][restPower])
                {
                    dist[nextCity][restPower] = nextCost;
                    q.emplace(nextCost, nextCity, restPower);
                }
            }
        }

        return -1;
    }
};